package mbsl.ui;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

import mbsl.util.SWTUtils;

import org.eclipse.swt.SWT;
import org.eclipse.swt.events.PaintEvent;
import org.eclipse.swt.events.PaintListener;
import org.eclipse.swt.graphics.GC;
import org.eclipse.swt.graphics.Point;
import org.eclipse.swt.layout.GridData;
import org.eclipse.swt.layout.GridLayout;
import org.eclipse.swt.widgets.Canvas;
import org.eclipse.swt.widgets.Composite;
import org.eclipse.swt.widgets.Display;
import org.eclipse.swt.widgets.Shell;

public class Tree extends Canvas {
	public Tree(final Composite pParent, int pStyle) {
		super(pParent, pStyle);
		
		mRoots = new ArrayList<Tree.TreeNode>();

		addPaintListener(new PaintListener() {
			@Override
			public void paintControl(PaintEvent pE) {
				GC gc = pE.gc;
				
				paint(gc);
			}
		});
		
		
		
		setColumns(DEFAULT_COLUMNS);
	}
	
	private void paint(GC gc) {
		gc.setAdvanced(true);
		
		int nodeCount = 0;
		
		for (TreeNode node : mRoots)
			nodeCount += countNodes(node);

		TreeNode[][] nodeMap = new TreeNode[nodeCount][mColumns];
		/** The queue holding the next node to visit in our BFS */
		Deque<TreeNode> nodeQueue = new ArrayDeque<TreeNode>();
		/** The list holding children who has children. */
		List<TreeNode> branches = new ArrayList<Tree.TreeNode>();
		/** The list holding childless children. */
		List<TreeNode> leaves = new ArrayList<Tree.TreeNode>();
		
		int row = 0;
		int rootColumn = (int)(ALIGN_LEFT ? Math.floor((double)(mColumns - 1) / 2) : Math.ceil((double)(mColumns - 1) / 2));
		
		for (TreeNode rootNode : mRoots) {
			nodeQueue.add(rootNode);
			
			putOnMap(gc, nodeMap, rootColumn, row, rootNode);
			
			while (!nodeQueue.isEmpty()) {
				TreeNode node = nodeQueue.poll();
				
				for (TreeNode child : node.getChildren())
					if (child.getChildren().length > 0)
						branches.add(child);
					else
						leaves.add(child);
				
				// TODO reduce by competitor size
				int spaceDown = 0 - nodeQueue.size(); // Only children with children are in the queue, and only children of the same parent, so they are competitors for space.
				
				for (int i = 0; i < mColumns; i++)
					if (nodeMap[node.y + 1][i] == null)
						spaceDown++;

				if (branches.size() == 1) {
					TreeNode child = branches.remove(0);
					
					putOnMap(gc, nodeMap, node.x, node.y + 1, child);
					
					nodeQueue.add(child);
					
					spaceDown--;
				} else if (branches.size() > 1) {
					System.out.println("branches.size() > 1");
				}
				
				if (leaves.size() <= spaceDown) {
					for (TreeNode child : leaves) {
						for (int i = 0; i < mColumns; i++) {
							if (!ALIGN_LEFT) // If we align left, we want it to check to the left first, and vice versa for the right
								i = -i;
							// So in these checks, we have to check both bounds, because either of them can go in either direction
							if (node.x - i >= 0 && node.x - i < mColumns && nodeMap[node.y + 1][node.x - i] == null) {
								putOnMap(gc, nodeMap, node.x - i, node.y + 1, child);
								break; // When we've placed this child, there's nothing more to do, so let's move to the next.
							} else if (i != 0 && node.x + 1 >= 0 && node.x + i < mColumns && nodeMap[node.y + 1][node.x + i] == null) {
								putOnMap(gc, nodeMap, node.x + i, node.y + 1, child);
								break;
							}
							
							i = Math.abs(i);
						}
					}
				} else {
					// TODO special case
				}
				
				branches.clear();
				leaves.clear();
			}
		}
	}
	private void drawLine(GC gc, TreeNode pFrom, TreeNode pTo) {
		gc.drawLine(pFrom.x * (BOX_WIDTH + MARGIN) + BOX_WIDTH / 2, pFrom.y * (BOX_HEIGHT + MARGIN) + BOX_HEIGHT, pTo.x * (BOX_WIDTH + MARGIN) + BOX_WIDTH / 2, pTo.y * (BOX_HEIGHT + MARGIN));
	}
	private void putOnMap(GC gc, TreeNode[][] pMap, int pX, int pY, TreeNode pNode) {
		pMap[pY][pX] = pNode;
		
		pNode.x = pX;
		pNode.y = pY;
		
		paintNode(gc, pNode, pX * (BOX_WIDTH + MARGIN), pY * (BOX_HEIGHT + MARGIN));
		
		if (!pNode.isRoot())
			drawLine(gc, pNode.getParent(), pNode);
	}
	private void paintNode(GC gc, TreeNode pNode, int pX, int pY) {
		// Set the line width
		gc.setLineWidth(BOX_BORDER_WIDTH);
		// Draw the border
		gc.drawRoundRectangle(pX + BOX_BORDER_WIDTH - 1, pY + BOX_BORDER_WIDTH - 1, BOX_WIDTH - BOX_BORDER_WIDTH + 1, BOX_HEIGHT - BOX_BORDER_WIDTH + 1, ARC_SIZE, ARC_SIZE);
		// Split the title on whitespace
		String[] words = pNode.getText().split("\\s+");
		// Each string in this array represents one line of text in the box
		List<String> lines = new ArrayList<String>(words.length);
		// Add the first word to the first line
		lines.add(words[0]);
		// The amount of pixels from the border of the area the box resides in, to where the text can start.
		int textPadding = 2 * BOX_BORDER_WIDTH - 2 * TEXT_MARGIN;
		// The capacity of the interior of the box, considering the text padding
		Point capacity = new Point(BOX_WIDTH - textPadding, BOX_HEIGHT - textPadding);
		// Put the words together again in lines that fit inside the capacity
		for (int i = 1; i < words.length; i++) {
			// If the current line and the next word together fit inside this capacity
			if (gc.stringExtent(lines.get(lines.size() - 1) + " " + words[i]).x < capacity.x)
// TODO chop the word up if it's longer than what's possible to fit
				// add it to the current line
				lines.set(lines.size() - 1, lines.get(lines.size() - 1) + " " + words[i]);
			// If not
			else
				// add it to a new line by itself
				lines.add(words[i]);
		}
		// The height of the total capacity available to each line of text.
		int lineHeight = capacity.y / lines.size();
		// Draw the lines of text
		for (int i = 0; i < lines.size(); i++) {
			Point size = gc.stringExtent(lines.get(i));

			int x = pX + textPadding + (capacity.x - size.x) / 2;

			int y = pY + textPadding + lineHeight * i + (lineHeight - size.y) / 2;

			gc.drawText(lines.get(i), x, y, true);
		}
	}
	/** Removes all nodes from the Tree */
	public void clear() {
		mRoots.clear();
	}
	/** The size of the brush used to paint the borders of the node boxes */
	private final int BOX_BORDER_WIDTH = 2;
	/** The margin used on text */
	private final int TEXT_MARGIN = 3;
	/** The margin between nodes in the graph */
	private final int MARGIN = 20;
	/** The width of the node boxes */
	private final int BOX_WIDTH = 84;
	/** The height of the node boxes */
	private final int BOX_HEIGHT = 40;
	/** The size of the arcs used on the round corners */
	private final int ARC_SIZE = 5;
	/** The default number of columns */
	private final int DEFAULT_COLUMNS = 3;
	/** Whether to align the table to the left (true) or right (false) */
	private final boolean ALIGN_LEFT = true;
	
	private List<TreeNode> mRoots;
	private int mColumns;
	
	public static void main(String[] pArgs) {
		Display display = new Display();
		
		Shell shell = new Shell(display);
		
		shell.setLayout(new GridLayout());
		
		final Tree s = new Tree(shell, SWT.NONE);
		
		s.setLayoutData(new GridData(SWT.FILL, SWT.FILL, true, true));
		
		TreeNode n1 = s.new TreeNode();
		TreeNode n2 = s.new TreeNode(n1);
		TreeNode n3 = s.new TreeNode(n1);
		TreeNode n4 = s.new TreeNode(n3);
		TreeNode n5 = s.new TreeNode(n3);
		TreeNode n6 = s.new TreeNode(n5);
		
		n1.setText("Monkey Island");
		n2.setText("Monkey Island: Special Edition");
		n3.setText("Monkey Island 2");
		n4.setText("Monkey Island 2: Special Edition");
		n5.setText("Curse of Monkey Island");
		n6.setText("Escape from Monkey Island");
		
		shell.setBounds(100, 100, 500, 100);
		shell.pack();
		shell.setVisible(true);
		
		SWTUtils.block(shell);
		
		display.dispose();
	}
	public void setColumns(int pColumns) {
		mColumns = pColumns;
	}
	public int getColumns() {
		return mColumns;
	}
	/**
	 * Counts the number of nodes in the subtree in which {@code pNode} is the root.
	 * @param pRoot The root node of the subtree
	 * @return The total number of children and children's children in the subtree.
	 */
	public int countNodes(TreeNode pRoot) {
		int count = 1;
		
		for (TreeNode node : pRoot.getChildren())
			count += countNodes(node);
		
		return count;
	}
	/**
	 * A node of a Tree.
	 * <p>
	 * Nodes cannot exist without a Tree, and using {@link #TreeNode()} will attach the new node to the Tree instance
	 * from which it came, as a root.
	 */
	public class TreeNode implements Comparable<TreeNode> {
		/**
		 * Attaches this node to the Tree as a root.
		 */
		public TreeNode() {
			this(null);
		}
		/**
		 * Attaches this node to the passed node as a child.
		 * <p>
		 * Passing {@code null} will add it to the Tree as a root.
		 */
		public TreeNode(TreeNode pNode) {
			if (pNode == null)
				mRoots.add(this);
			else
				setParent(pNode);
			
			x = SWT.DEFAULT;
			y = SWT.DEFAULT;
		}
		/** Returns this node's children as an array of TreeNodes, or an empty such array if it has none. */
		public TreeNode[] getChildren() {
			if (mChildren == null || mChildren.size() == 0)
				return new TreeNode[0];
			else
				return mChildren.toArray(new TreeNode[mChildren.size()]);
		}
		/** Returns {@code true} if and only if this node doesn't have a parent node. */
		public boolean isRoot() {
			return mParent == null;
		}
		/** Returns the root of the tree to which this node belongs. */
		public TreeNode getRoot() {
			if (isRoot())
				return this;
			
			TreeNode node = mParent;
			
			while (!node.isRoot())
				node = node.getParent();
			
			return node;
		}
		/** Returns {@code true} if the passed node is a descendant of this node. */
		public boolean isDescendant(TreeNode pNode) {
			for (TreeNode node : getChildren()) {
				if (node == pNode)
					return true;
				else
					return node.isDescendant(pNode);
			}
			
			return false;
		}
		/** Returns the parent of this node, or {@code null} if it is a root node. */
		public TreeNode getParent() {
			return mParent;
		}
		/** 
		 * Sets the passed node as the parent of this one.
		 * <p>
		 * Passing {@code null}, will register the node as a root.
		 * <p>
		 * This method will throw a RuntimeException if the passed node is:
		 * <ul>
		 * <li>The child node, or
		 * <li>A descendant of the child node
		 * </ul>
		 */
		public void setParent(TreeNode pParent) {
			if (mParent == pParent) // If they're alike, we don't have to do anything
				return;
			
			if (pParent != null) { // If the new parent isn't null, we have to add ourselves to its child list
				if (pParent == this)
					throw new IllegalArgumentException("A node cannot be its own parent.");
				if (isDescendant(pParent))
					throw new IllegalArgumentException("A node cannot have one of its descendants as a parent.");
				
				pParent.addChild(this);
			} else // If it is null, it means we're supposed to be a root, so we'd better add ourselves to the root list
				mRoots.add(this);

			if (mParent != null) // If the current parent isn't null, we have to remove ourselves from its child list
				mParent.removeChild(this);
			else // If it is null, it means we were a root, so we'd better remove ourselves from the root list
				mRoots.remove(this);
			
			mParent = pParent;
		}
		/** Sets the node text to {@code pText}. */
		/** 
		 * Sets the text in this node.
		 * @see #getText()
		 */
		public void setText(String pText) {
			mText = pText;
		}
		/**
		 * Returns the text used in this node.
		 * <p>
		 * If {@linkplain #setText(String)} hasn't been used, it will call toString() on
		 * the object set with {@linkplain #setData(Object)}.  If no object is set, it
		 * will return {@code null}.
		 */
		public String getText() {
			if (mText != null)
				return mText;
			else if (mData != null)
				return mData.toString();
			else
				return null;
		}
		/** 
		 * Attaches the passed object to the node.
		 * <p>
		 * If {@linkplain #setText(String)} is {@code null}, this object will be used to determine the text of the node via toString().
		 * @see #getText()
		 */
		public void setData(Object pData) {
			mData = pData;
		}
		/** 
		 * Retrieves the attached object from the node.
		 * <p>
		 * If no object is attached, {@code null} is returned. To clear the attachment, pass {@code null} to {@link #setData(Object)}.
		 */
		public Object getData() {
			return mData;
		}

		/** Adds a child to the child list. */
		private void addChild(TreeNode pChild) {
			if (mChildren == null)
				mChildren = new ArrayList<Tree.TreeNode>();
			
			mChildren.add(pChild);
		}
		/** Removes a child from the child list. */
		private void removeChild(TreeNode pChild) {
			mChildren.remove(pChild);
			
			if (mChildren.isEmpty())
				mChildren = null;
		}
		
		private int x;
		private int y;
		private String mText;
		private List<TreeNode> mChildren;
		private TreeNode mParent;
		private Object mData;
		@Override
		public int compareTo(TreeNode pO) {
			return getText().compareTo(pO.getText());
		}
	}
}